import { testSort, measureSort } from "./utils";

function heapSort(arr: number[]) :number[] {
  let n = arr.length;
  // 原地建堆
  // 1. 找到最后节点的父节点
  const start = Math.floor(n / 2 - 1);

  // 多次下滤操作获取堆
  for (let i = start; i >= 0; i--) {
    heapify_down(arr, n, i);
  }

  for(let i = n-1; i> 0; i--){
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapify_down(arr, i, 0 )
  }
  return arr;
}

function heapify_down(arr: number[], n: number, i: number) {
  while (i * 2 + 1 < n) {
    const leftDot = i * 2 + 1;
    const rightDot = i * 2 + 2;
    let currentDot = leftDot;

    if (arr[leftDot] < arr[rightDot] && rightDot < n) {
      currentDot = rightDot;
    }
    if (arr[currentDot] > arr[i]) {
      [arr[currentDot], arr[i]] = [arr[i], arr[currentDot]];
      i = currentDot;
    } else {
      break;
    }
    heapify_down(arr, n, i);
  }
}

// console.log(heapSort([14, 46, 152, 168, 37, 136, 72, 97, 82, 120]));

// 测试
testSort(heapSort);
// 测试时间
measureSort(heapSort, 100000);
